Problem statement: zenit12ckf

Na takej farme je veľký ruch. Neustále sa niečo prenáša, vybavuje, rieši, hasí, kazí a opravuje. Dobrá organizácia dopravy je pre bezchybný a efektívny chod kľúčová.

Farmár Maják podozrieva niektorých svojich zamestnancov, že hospodárske stroje využívajú na výlety za dievčatami. To by ste totiž netušili, akému obdivu sa budete tešiť, ak prídete za svojou slečnou na takom traktore! Aby predišiel podobným situáciám, rozhodol sa začať s kontrolami tachometrov. Na vstupe sú informácie o vzdialenostiach hospodárskych budov a dôležitých lokalít a postupnosť miest, ktoré dnes musí daný hospodársky stroj navštíviť. Vypočítajte očakávanú prejdenú vzdialenosť.

Na prvom riadku vstupu sú dve celé čísla: počet budov N a počet ciest M medzi nimi. Platí 2 ≤ N ≤ 500 a 1 ≤ M ≤ 50,000. Aby sme sa vyhli slovným pomenovaniam ako garáž, kravín či sklad, tak si očíslujeme budovy od 1 po N.

Nasleduje M riadkov, na každom sú tri celé čísla x,y,z. Platí 1 ≤ x,y ≤ N, x ≠ y, 1 ≤ z ≤ 1000. Tieto tri čísla hovoria, že medzi miestami s číslami x a y existuje obojsmerná priama cesta s dĺžkou z metrov. Medzi každou dvojicou miest sa vyskytne najviac jedna priama cesta. Nepredpokladajte nič typu trojuholníková nerovnosť. Dĺžky ciest medzi budovami spolu nijako nesúvisia.

Na ďalšom riadku je číslo K (2 ≤ K ≤ 1000), označujúce počet zastávok hospodárskeho stroja. Na poslednom riadku vstupu je popis putovania tohto stroja v tvare b₁ − b₂ − …− b_K. Pred aj za každou pomlčkou (znak mínus, ASCII kód 45) je práve jedna medzera. Každé z čísel na tomto riadku je medzi 1 a N. Tento popis znamená, že stroj začína na mieste s číslom b₁, potom sa presúva k miestu b₂, potom k b₃ a tak ďalej, až kým neskončí na b_K. Stroj s výnimkou ciest neprekonáva žiadnu vzdialenosť. V tejto postupnosti sa nevyskytnú dve rovnaké čísla za sebou. Stroj pri presune z jedného objektu k druhému používa priame spojenie. Môžete predpokladať, že z každého objektu na tomto putovaní existuje priama cesta do jeho nasledovníka. Na jediný riadok výstupu vypíšte jedno číslo: prejdený počet metrov na konci dňa.

4 6
1 2 40
3 2 10
4 2 90
1 4 10
3 1 20
3 4 40
4
1 - 2 - 4 - 1

    
  

140

    
  

3 3
1 2 15
3 2 27
3 1 6
5
3 - 2 - 1 - 2 - 1

    
  

72

    
  

4 5
3 1 14
3 2 19
1 4 12
4 2 13
3 4 9
5
2 - 3 - 4 - 1 - 3

    
  

54